/**
 * 2016年10月28日
 */
package algorithm;

import java.util.Deque;
import java.util.Queue;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.ArrayDeque;
import java.util.ArrayList;
class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(num!=null){
            Deque<Integer> dq = new ArrayDeque<Integer>();
            for(int i=0;i<size;i++){
                while(!dq.isEmpty() && num[i]>num[dq.peekLast()]){
                    dq.pollLast();
                }
                dq.offerLast(i);
            }
			for(int i=size;i<num.length;i++){
                res.add(num[dq.peekFirst()]);
                while(!dq.isEmpty() && num[i]>=num[dq.peekLast()])
                    dq.pollLast();
                if(!dq.isEmpty() && dq.peekFirst() <=(i-size)){
                    dq.pollFirst();
                }
                dq.offerLast(i);
            }   
            res.add(num[dq.peekFirst()]);
            
        }
        return res;
    }
}
public class SlidingWindowMax {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		AtomicInteger ai;
		int arr [] = new int []{2,3,4,2,6,2,5,1};
		Solution s = new Solution();
		for(int i:s.maxInWindows(arr, 3)){
			System.out.println(i);
		}

	}

}
